package ee.serge;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import ee.ttu.serge.container.priorityqueue.PriorityQueue;
import ee.ttu.serge.container.stack.Stack;

public class Main {

   public static void main(String[] args) {
      try {
         new Main();
      } catch (IOException e) {
         e.printStackTrace();
      }
   }
   
   public Main() throws IOException {
      /*Random rnd = new Random();
      while (true) {
         List<KnapsackObject> list = new ArrayList<KnapsackObject>();
         for (int i = 0; i < 30; i++) {
            KnapsackObject obj = new KnapsackObject(rnd.nextInt(50) + 1, rnd.nextInt(50) + 1);
            list.add(obj);
         }
         Collections.sort(list);
         
         
         long time = System.currentTimeMillis();
         int a = knapsackDepthFirst(list, 150);
         long timeA = System.currentTimeMillis() - time;
         time = System.currentTimeMillis();
         int b = knapsackDepthFirstGreedy(list, 150);
         long timeB = System.currentTimeMillis() - time;
         System.out.println((float)timeA / timeB);
         if (a != b) {
            System.out.println(">" + calculateGreedy(list, 0, 0, 25));
            System.out.println(">" + a);
            System.out.println(">" + b);
            System.out.println(list);
            break;
         }
      }*/
      List<KnapsackObject> list = FileHelper.read("70.in");
      Collections.sort(list);
      FileHelper.write("OUT.out", knapsackDepthFirstGreedy(list, 750));
      System.out.println("DONE");
      //System.out.println(">" + calculateGreedy(list, 0, 0, 50) + " (Greedy)");
      //System.out.println(">" + knapsackDepthFirstGreedy2(list, 50).getObjectsTaken() + " (DF Greedy)");
      //System.out.println(">" + knapsackDepthFirst2(list, 1750).getPrice() + " (DF)");
   }
   
   private KnapsackState knapsackDepthFirst(final List<KnapsackObject> listOfAllItems, final int maxWeight) {
      Stack<KnapsackState> states = new Stack<KnapsackState>();
      states.push(new KnapsackState(listOfAllItems, new ArrayList<KnapsackObject>(), 0, 0));
      KnapsackState maxState = new KnapsackState(null, new ArrayList<KnapsackObject>(), 0, Integer.MIN_VALUE);
      while (!states.isEmpty()) {
         KnapsackState state = states.pop();
         for (int i = 0; i < state.getObjectsLeft().size(); i++) {
            KnapsackObject item = state.getObjectsLeft().get(i);
            if (state.getWeight() + item.getWeight() <= maxWeight) {
               List<KnapsackObject> newTakenList = new ArrayList<KnapsackObject>(state.getObjectsTaken());
               newTakenList.add(item);
               KnapsackState newState = new KnapsackState(
                     state.getObjectsLeft().subList(i + 1, state.getObjectsLeft().size()),
                     newTakenList,
                     state.getWeight() + item.getWeight(), 
                     state.getPrice() + item.getPrice());
               states.push(newState);
               if (newState.getPrice() > maxState.getPrice()) {
                  maxState = newState;
               }
            }
         }
      }
      return maxState;
   }
   
   private KnapsackState knapsackDepthFirstGreedy(final List<KnapsackObject> listOfAllItems, final int maxWeight) {
      PriorityQueue<KnapsackState> states = new PriorityQueue<KnapsackState>();
      states.enqueue(new KnapsackState(listOfAllItems, new ArrayList<KnapsackObject>(), 0, 0, calculateGreedy(listOfAllItems, 0, 0, maxWeight)));
      KnapsackState maxState = new KnapsackState(listOfAllItems, new ArrayList<KnapsackObject>(), 0, Integer.MIN_VALUE, 0);
      while (!states.isEmpty()) {
         KnapsackState state = states.dequeue();
         for (int i = 0; i < state.getObjectsLeft().size(); i++) {
            KnapsackObject item = state.getObjectsLeft().get(i);
            int weight = state.getWeight() + item.getWeight();
            if (weight <= maxWeight) {
               List<KnapsackObject> newObjectsLeftList = state.getObjectsLeft().subList(i + 1, state.getObjectsLeft().size());
               int price = state.getPrice() + item.getPrice();
               float greedy = calculateGreedy(newObjectsLeftList, price, weight, maxWeight);
               if (greedy >= maxState.getPrice()) {
                  List<KnapsackObject> newObjectsTakenList = new ArrayList<KnapsackObject>(state.getObjectsTaken());
                  newObjectsTakenList.add(item);
                  KnapsackState newState = new KnapsackState(newObjectsLeftList, newObjectsTakenList, weight, price, greedy);
                  states.enqueue(newState);
                  if (price > maxState.getPrice()) {
                     maxState = newState;
                  }
               }
            }
         }
      }
      return maxState;
   }
   
   private float calculateGreedy(List<KnapsackObject> list, int price, int weight, int maxWeight) {
      for (KnapsackObject item : list) {
         if (weight + item.getWeight() > maxWeight) {
            int remainingWeight = maxWeight - weight;
            return price + remainingWeight * item.getValue();
         }
         weight += item.getWeight();
         price += item.getPrice();
      }
      return price;
   }
   
}
